package com.example.array.doublepointer;

import java.util.*;

/**
 * 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
 *  输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
 *  翻转后单词间应当仅用一个空格分隔。
 *  翻转后的字符串中不应包含额外的空格。
 *
 * 输入：s = "  hello  world   "
 * 输出："world hello"
 * 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
 */
public class Leetcode151_ReverseWords {
    public static void main(String[] args) {
        System.out.println("res :" + reverseWords2("the sky is blue"));
    }

    /**
     * 解法一:暴力解法(使用JAVA api解决)
     *
     * @param s
     * @return
     */
    public static String reverseWords1(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String[] splits = s.split("\\s+");
        List<String> stringList = Arrays.asList(splits);
        Collections.reverse(stringList);
        return String.join(" ", stringList);
    }

    /**
     * 优化解法：数组+双指针
     *
     * 1.按字符串长度定义新数组，临时存储
     * 2.倒序遍历字符串，定位单词起止索引
     * 3.读取单词起止索引范围内的字符，写入新数组
     * 4.还原指针，用以定位下个单词
     * 5.将新数组中合法数据生成新字符串
     *
     * 边界问题
     * 以字符串中的空格为单词分界
     * 字符串首尾的空格应跳过
     * 细节问题
     * 倒序遍历时，先定义单词尾指针
     * 读取到下一个空格，索引+1定位单词开始指针
     * 注意单词间的多个空格，只保留一个
     *
     */
    public static String reverseWords2(String s) {
        int len;
        if (s == null || (len =s.length()) == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        int left = - 1;
        int right = - 1;

        for (int i = len - 1; i >= 0; i--) {
            char ch = s.charAt(i);

            // 从后向前遍历，根据是否为' '
            // 分别别定位单词的起止索引
            if (ch != ' ') {
                if (right == -1) { // 定位单词的结尾索引
                    right = i;
                }
                if (i == 0) {
                    left = i; // 细节：处理字符串首字符不是空格
                }
            } else {
                // right != -1 说明单词的结尾索引已经找到
                // 定位单词的开始索引
                if (right != -1) {
                    left = i + 1;
                }
            }
            // 将定位了的单词加入到临时数组中
            if (left >= 0 && right >= 0) {
                System.out.println(left + "  " + right);
                while (left <= right) {
                    sb.append(s.charAt(left++));

                }
                // 给每个单词后面放一个' '
                sb.append(' ');
                // 还原单词索引
                right = left = -1;
                System.out.println(sb);
            }
        }

        return sb.toString().trim();
    }

    /**
     * 解法三：双端队列解法思路分析
     * 1.往双端队列头部依次存入每个单词
     * 以空格为单词分界，将单词字符存入缓冲区
     * 从缓冲区取出单词存入双端队列头部
     * 注意过滤掉首尾、单词间多余空格
     * 2.从双端队列头部依次取出每个单词
     * 使用join方法，将空格拼接到每个单词之间
     * 注意不要遗漏最后一个单词
     *
     * @param s
     * @return
     */
    public static String reverseWords3(String s) {
        int left = 0, right = s.length() - 1;
        Deque<String> d = new LinkedList<>();
        StringBuilder word = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ') {
                word.append(c);
            } else {
                if (word.length() != 0) { // 到达了单词结尾
                    d.offerFirst(word.toString());
                    word.setLength(0);
                }
            }
            ++left;
        }
        if (word.length() > 0) {
            d.offerFirst(word.toString());
        }
        return String.join(" ", d);
    }
}
